《算法设计与分析》期末试卷B (精选03)

一、基础概念简答题（每题 5 分，共 4 小题，共 20 分）

1. 请阐述大 (O) 算法复杂度的定义。（5 分）

查看答案与解析

答案：
若存在常数 (c>0) 与正整数 (n_0)，使得当 (n\ge n_0) 时恒有 [ T(n)\le c\cdot f(n), ] 则称 (T(n)=O(f(n)))。

解析（步骤化表述）：

• 第一步：说明比较对象：将算法的运行时间（或基本操作次数）记为 (T(n))，与一个“参照函数” (f(n)) 做渐近比较。
• 第二步：给出“最终上界”条件：从某个规模 (n_0) 之后，(T(n)) 始终被 (c\cdot f(n)) 这个函数上界控制。
• 第三步：解释含义：(O(f(n))) 描述的是渐近上界（增长阶），忽略常数因子与低阶项，用于刻画规模变大时的增长趋势。

---

难度：⭐
考点：#渐近复杂度 #大O记号 #上界

💡 学习锦囊

📖 相关公式与知识点：

• (T(n)=O(f(n)) \iff \exists c>0,\exists n_0,\forall n\ge n_0: T(n)\le c f(n))
• 常用符号对比：(O)（上界）、(\Omega)（下界）、(\Theta)（紧界）

思路分析

看到“大 (O)”先写“存在 (c,n_0)，然后是“对所有足够大的 (n)”的上界不等式，这是最标准的定义模板。

易错点

• 把 (O) 当成“等于”，写成 (T(n)=c f(n))（错误）
• 忘记“当 (n\ge n_0)”的条件（渐近意义）

🔄 举一反三

1. 判断：(3n^2+5n+7 = O(n^2)) 是否成立？
   查看练习答案与解析

   答案：成立。
   解析： [ 3n^2+5n+7 \le 3n^2+5n^2+7n^2 = 15n^2 \quad (\forall n\ge 1) ] 取 (c=15,n_0=1)，故 (3n^2+5n+7 = O(n^2))。

2. 判断：(n^2 = O(n)) 是否成立？
   查看练习答案与解析

   答案：不成立。
   解析： 若 (n^2\le c n) 对足够大 (n) 成立，则 (n\le c) 对足够大 (n) 成立，矛盾。

2. 请阐述回溯算法基本思想。（5 分）

查看答案与解析

答案：
回溯法是在状态空间树上进行深度优先搜索，按约束条件逐步构造解；当发现当前部分解不可能扩展为可行解/最优解时，立即剪枝并回退到上一步继续搜索其他分支。

解析（关键点拆解）：

• 状态表示：用“部分解”作为结点（例如选择了前 (k) 个决策）。
• 扩展策略：沿一条路径不断做选择（DFS）。
• 约束检查：一旦违反约束/不可能更优，停止向下扩展。
• 回退机制：撤销最近一次选择，尝试下一种选择，直至遍历完可能性或找到最优。

---

难度：⭐
考点：#回溯法 #状态空间树 #深度优先搜索 #剪枝

💡 学习锦囊

📖 相关公式与知识点：

• 回溯 = DFS + 约束检查 + 撤销选择（回退）
• 常见剪枝：可行性剪枝、界限剪枝（分支限界思想）

思路分析

回溯题回答时抓住“四件事”：树、深搜、剪枝、回退，并点明“边搜索边构造”即可。

🔄 举一反三

1. 列举 2 个常用回溯问题。
   查看练习答案与解析

   答案： 八皇后、0/1 背包（回溯版）、图着色、全排列、子集和等。
   解析： 这些问题都能自然表示为“逐步选择”的状态空间树，且存在大量无效分支可剪枝。

3. 请解释什么是最优子结构性质？（5 分）

查看答案与解析

答案：
若一个问题的最优解能够由其子问题的最优解组合得到（即最优解包含子问题最优解），则称该问题具有最优子结构性质。

解析：

• 该性质是动态规划/贪心法能成立的关键前提之一。
• 典型例子：最短路径、矩阵连乘、最优二叉搜索树等。

---

难度：⭐
考点：#动态规划 #最优子结构 #子问题

💡 学习锦囊

📖 相关公式与知识点：

• 有最优子结构 (\ne) 一定能用 DP：还需要“子问题重叠”（或可分解递推）

思路分析

答题模板：先一句“最优解由子问题最优解组成”，再补一句“这是 DP/贪心适用的重要条件”即可。

🔄 举一反三

1. 举例说明“无最优子结构”的情形。
   查看练习答案与解析

   答案： 例如某些带全局约束/路径依赖的决策问题，局部最优选择会改变后续可行集合，导致子问题的“最优”不一定能拼成整体最优。
   解析： 关键是“最优解的组成部分”在整体环境变化后不再保持最优。

4. 简述利用分治法求解的基本步骤。（5 分）

查看答案与解析

答案：
分治法一般包含三步：分解（Divide）、解决（Conquer）、合并（Combine），通常以递归方式实现。

解析（按标准三段式）：

1. 分解：将原问题划分为若干规模更小、相互独立、形式相同的子问题。
2. 求解：对子问题递归求解；若子问题足够小则直接求解（递归基）。
3. 合并：将子问题解合并得到原问题解。

---

难度：⭐
考点：#分治法 #递归 #分解与合并

💡 学习锦囊

📖 相关公式与知识点：

• 典型递推：(T(n)=aT(n/b)+g(n))，可用主定理分析

🔄 举一反三

1. 给出 2 个经典分治算法例子。
   查看练习答案与解析

   答案： 归并排序、快速排序、二分查找（思想）、Strassen 矩阵乘法等。
   解析： 都满足“分解为同类小问题 + 合并/汇总”的结构。

---

二、分析题（每题 10 分，共 3 小题，共 30 分）

1. 求解递推关系：当 (n\ge 1) 时 (f(n)=3f(n-1))，且 (f(0)=5)。（10 分）

查看答案与解析

答案： (f(n)=5\cdot 3^n)。

解析（完整推导）： [ \begin{aligned} f(n) &= 3f(n-1) \ &= 3\cdot 3 f(n-2)=3^2 f(n-2) \ &\ \ \vdots \ &= 3^n f(0) \ &= 3^n \cdot 5 = 5\cdot 3^n \end{aligned} ]

---

难度：⭐
考点：#递推关系 #等比递推 #数学归纳/展开法

💡 学习锦囊

📖 相关公式与知识点：

• 一阶齐次线性递推：(f(n)=a f(n-1)\Rightarrow f(n)=f(0)a^n)

思路分析

这类题最稳的方法是“不断展开到 (f(0))”，每展开一层就多乘一个 3。

🔄 举一反三

1. 若 (g(n)=2g(n-1)), (g(1)=3)，求 (g(n))。
   查看练习答案与解析

   答案： (g(n)=3\cdot 2^{n-1})。
   解析： (g(n)=2^{n-1}g(1)=3\cdot 2^{n-1})。

2. 若 (h(n)=5h(n-1)), (h(0)=1)，求 (h(n))。
   查看练习答案与解析

   答案： (h(n)=5^n)。
   解析： 同上。

2. 分析下列算法的时间复杂度。（10 分）

void fun(int n)
{
    int s = 0, i, j, k;
    for (i = 0; i <= n; i++)
        for (j = 0; j <= i; j++)
            for (k = 0; k < j; k++)
                s++;
}

查看答案与解析

答案： 时间复杂度为 (O(n^3))。

解析（按基本语句计数）： 基本操作为 s++，执行次数 [ \begin{aligned} f(n) &= \sum_{i=0}^{n}\sum_{j=0}^{i}\sum_{k=0}^{j-1}1 = \sum_{i=0}^{n}\sum_{j=0}^{i} j = \sum_{i=0}^{n}\frac{i(i+1)}{2} \ &= \frac12\left(\sum_{i=0}^{n}i^2+\sum_{i=0}^{n}i\right) = \frac12\left(\frac{n(n+1)(2n+1)}{6}+\frac{n(n+1)}{2}\right) = \Theta(n^3) \end{aligned} ] 因此时间复杂度为 (O(n^3))。

---

难度：⭐⭐
考点：#时间复杂度 #三重循环 #求和化简

💡 学习锦囊

📖 相关公式与知识点：

• (\sum_{i=1}^{n} i = \frac{n(n+1)}{2})
• (\sum_{i=1}^{n} i^2 = \frac{n(n+1)(2n+1)}{6})

思路分析

看到“j 依赖 i、k 依赖 j”的嵌套，先把最内层化成 (j)，再一步步往外求和，最后用已知求和公式或阶数量级判断。

易错点

• 误把最内层循环当成 (n) 次，从而得出 (O(n^3)) 的“偶然正确但过程错误”
• 忘记 (j) 从 0 到 i（依赖关系导致求和上限变化）

🔄 举一反三

1. 若把最内层改成 for (k = 0; k < i; k++)，复杂度是多少？
   查看练习答案与解析

   答案： (O(n^3))。
   解析： 执行次数 (\sum_{i=0}^{n}\sum_{j=0}^{i} i = \sum_{i=0}^{n}(i+1)i = \Theta(n^3))。

3. 下面算法用于在带头结点的单链表 h 中查找第 1 个值为 x 的结点，找到后返回其逻辑序号（从 1 计起），否则返回 0。分析该算法存在的问题。（10 分）

typedef struct node {
    int data;
    struct node *next;
} LNode;

int findx(LNode *h, int x) {
    LNode *p = h->next;
    int i = 0;
    while (p->data != x) {
        i++;
        p = p->next;
    }
    return i;
}

查看答案与解析

答案（主要问题）：

1. 序号计数错误：若首元结点（第 1 个数据结点）就是 (x)，此实现返回 0，但应返回 1。
2. 空指针风险：当链表中不存在值为 (x) 的结点时，p 会变为 NULL，继续访问 p->data 会发生错误（程序崩溃）。

解析（如何修正的要点）：

• 先判空再取值：循环条件应包含 p != NULL。
• 序号从 1 开始：可以初始化 i = 1，或在返回时 return i+1，但需与循环一致。

一种正确写法示例：

int findx(LNode *h, int x) {
    LNode *p = h->next;
    int i = 1;
    while (p != NULL) {
        if (p->data == x) return i;
        p = p->next;
        i++;
    }
    return 0;
}

---

难度：⭐⭐
考点：#链表 #健壮性 #空指针 #边界条件

💡 学习锦囊

📖 相关公式与知识点：

• 指针类代码：先判断指针有效，再解引用
• 逻辑序号：明确“从 0 还是从 1”并保持一致

易错点

• “while(p->data!=x)” 把 NULL 情况漏掉，属于典型健壮性错误

🔄 举一反三

1. 若要返回“前驱结点指针”，应如何改写？
   查看练习答案与解析

   答案： 用 prev 指针跟随 p，当 p->data==x 时返回 prev。若不存在则返回 NULL。
   解析： 遍历时保持不变式：prev->next == p。

---

三、解答题（每题 8 分，共 4 小题，共 32 分）

1. 两机流水作业调度（Johnson 法则）。（8 分）

若 (n=4)，作业 (i) 在机器 (M_1)、(M_2) 上加工时间分别为 (a_i)、(b_i)，且
((a_1,a_2,a_3,a_4)=(4,5,12,10))，((b_1,b_2,b_3,b_4)=(8,2,15,9))。
求 4 个作业的最优调度方案，并计算最优值（完工时间 (C_{\max})）。

查看答案与解析

答案： 一种最优序列为 ((1,3,4,2))，最优完工时间 (C_{\max}=42)。另外 ((1,3,2,4)) 也可达到同样的最优值。

解析（Johnson 法则步骤）：

1. 在所有未安排作业的 ({a_i,b_i}) 中找最小值。
2. 若最小值来自某作业的 (a_i)，将该作业放到序列最前端（从左往右填）；
   若最小值来自某作业的 (b_i)，将该作业放到序列最后端（从右往左填）。
3. 重复直到所有作业排完。

对本题执行：

• 最小值为 (a_1=4) → 放最前：([1,_,_,_])
• 余下最小值为 (b_2=2) → 放最后：([1,_,_,2])
• 余下作业 3、4：最小值为 (b_4=9) → 放倒数第二：([1,_,4,2])
• 剩下作业 3 → 填入：([1,3,4,2])

计算 (C_{\max})（两机流水规则）：

作业序列	1	3	4	2
(M_1) 完成时刻	4	16	26	31
(M_2) 完成时刻	12	31	40	42

因此 (C_{\max}=42)。

---

难度：⭐⭐
考点：#Johnson法则 #两机流水作业 #调度

💡 学习锦囊

📖 相关公式与知识点：

• 两机 Johnson 规则可保证最小化 (C_{\max})（两机情形最优）
• 计算完工时间时：
  (M_1) 连续加工；(M_2) 开始时间 = (\max{M_1) 该作业完成时刻, (M_2) 上一作业完成时刻(})

易错点

• 把“最小的 (b_i)”放到前面（方向搞反）
• 计算 (M_2) 开始时忘取 (\max)

🔄 举一反三

1. 若只有 3 个作业，给定时间后如何快速验证序列是否最优？
   查看练习答案与解析

   答案： 直接用 Johnson 得到序列，再与其他 (3!=6) 个序列逐一算 (C_{\max}) 对比即可。
   解析： 小规模可用枚举验证 Johnson 结果。

2. 回溯法解 0/1 背包问题。（8 分）

使用回溯法解 0/1 背包问题：(n=3)，容量 (C=9)，价值 (V={6,10,3})，重量 (W={3,4,4})。
解空间由长度为 3 的 0-1 向量组成，要求用完全二叉树表示解空间（从根出发，左 1 右 0），并求最优值与最优解。

查看答案与解析

答案： 最优解 ((1,1,0))，最优值 (16)，总重量 (7\le 9)。

解析（列举可行解并比较）： 向量 ((x_1,x_2,x_3)) 表示是否选择第 (i) 件物品。

向量	重量 (3x_1+4x_2+4x_3)	价值 (6x_1+10x_2+3x_3)	可行性
(0,0,0)	0	0	可行
(0,0,1)	4	3	可行
(0,1,0)	4	10	可行
(0,1,1)	8	13	可行
(1,0,0)	3	6	可行
(1,0,1)	7	9	可行
(1,1,0)	7	16	可行且最优
(1,1,1)	11	19	不可行（超重）

回溯树（左 1 右 0 的决策顺序示意）：

• 根：((_,_,_))
  • 左选 (x_1=1) → ((1,_,_))
    • 左选 (x_2=1) → ((1,1,_))
      • 左选 (x_3=1) → ((1,1,1)) 超重剪枝
      • 右选 (x_3=0) → ((1,1,0)) 价值 16（当前最优）
    • 右选 (x_2=0) → ((1,0,_))（继续…）
  • 右选 (x_1=0) → ((0,_,_))（继续…）

回溯法（递归）伪代码（与“左 1 右 0”一致）：

bestV = 0, bestX = (0,0,0)
DFS(i, cw, cv, x[1..n]):
    if cw > C: return              // 可行性剪枝：超重
    if i > n:
        if cv > bestV: bestV=cv, bestX=x
        return
    x[i]=1; DFS(i+1, cw+w[i], cv+v[i], x)   // 左分支：选
    x[i]=0; DFS(i+1, cw,       cv,     x)   // 右分支：不选

本题规模很小（(n=3)），用回溯遍历到所有叶子结点即可得到最优解；若 (n) 更大，可再加入“上界剪枝”（例如用剩余物品价值上界估计）。

---

难度：⭐⭐
考点：#0-1背包 #回溯法 #剪枝 #解空间树

💡 学习锦囊

📖 相关公式与知识点：

• 约束：(\sum w_i x_i \le C)
• 目标：(\max \sum v_i x_i)
• 常用剪枝：
  • 可行性剪枝（超重即剪）
  • 上界剪枝（用“剩余物品价值上界”估计，若不可能超过当前最优则剪）

🔄 举一反三

1. 若 (C=8)，本题最优解会变吗？
   查看练习答案与解析

   答案：不变，仍为 ((1,1,0))，重量 7 可行且价值 16 最大。
   解析： ((0,1,1)) 价值 13；((1,0,1)) 价值 9；((1,1,0)) 仍最好。

3. 活动选择（区间调度）问题。（8 分）

共有 10 位客户申请租用羽毛球场，区间为 ((s(i),f(i)))。同一时刻只能租给一位客户。请设计安排方案使满足客户数最多，并给出最多可安排人数。

i	1	2	3	4	5	6	7	8	9	10
s(i)	0	3	1	5	3	5	11	8	8	6
f(i)	6	5	4	9	8	7	13	12	11	10

查看答案与解析

答案： 最多可安排 4 位客户，例如选择客户 ({3,6,9,7}) 对应区间 ((1,4),(5,7),(8,11),(11,13))。

解析（贪心策略）： 按结束时间 (f(i)) 从小到大排序，依次选择与已选区间不冲突（开始时间 (\ge) 上一个结束时间）的活动。

按 (f) 排序：

顺序	客户 i	(s,f)
1	3	(1,4)
2	2	(3,5)
3	1	(0,6)
4	6	(5,7)
5	5	(3,8)
6	4	(5,9)
7	10	(6,10)
8	9	(8,11)
9	8	(8,12)
10	7	(11,13)

选择过程：

• 选 (1,4)（客户 3）
• 下一个起点 (\ge 4) 的最早结束是 (5,7)（客户 6）
• 下一个起点 (\ge 7) 的最早结束是 (8,11)（客户 9）
• 下一个起点 (\ge 11) 的是 (11,13)（客户 7）

共 4 个，且贪心可证最优。

---

难度：⭐⭐
考点：#贪心算法 #活动选择 #区间调度

💡 学习锦囊

📖 相关公式与知识点：

• 经典结论：按结束时间最早优先的贪心策略可得到最大兼容集合

易错点

• 排序时把开始时间当关键字（会导致非最优）
• 冲突判定用 “(>)” 而非 “(\ge)”（边界要看题意是否允许端点相接）

🔄 举一反三

1. 若要求“区间端点相接也算冲突”，应怎么改判定？
   查看练习答案与解析

   答案： 把“可选条件”从 (s \ge f_{\text{last}}) 改为 (s > f_{\text{last}})。
   解析： 端点相接冲突意味着必须严格大于。

4. 8 人循环赛赛程表设计（分治思想）。（8 分）

8 位运动员进行循环赛，要求：
（1）每位选手与其他各赛一次；（2）每位选手每天只赛一次；（3）共进行 (n-1=7) 天。
请给出一个合理赛程表。

查看答案与解析

答案： 以下为一个可行赛程（“圆圈法/分治构造”均可得到同类表）。

天数	对阵 1	对阵 2	对阵 3	对阵 4
Day1	1-8	2-7	3-6	4-5
Day2	1-7	8-6	2-5	3-4
Day3	1-6	7-5	8-4	2-3
Day4	1-5	6-4	7-3	8-2
Day5	1-4	5-3	6-2	7-8
Day6	1-3	4-2	5-8	6-7
Day7	1-2	3-8	4-7	5-6

验证要点：

• 每天每人只出现一次（不重复参赛）。
• 每一对选手恰好出现一次（全覆盖）。
• 共 7 天完成（(n-1) 天）。

---

难度：⭐⭐
考点：#循环赛赛程 #分治法 #构造法

💡 学习锦囊

📖 相关公式与知识点：

• (n) 为偶数时，一天可安排 (n/2) 场；总场次 (n(n-1)/2)，共 (n-1) 天刚好排满

思路分析

圆圈法本质上是一个“结构化构造”：固定 1 号，其余循环位移；分治法也可把 8 人分成 4+4，再递归合并对阵关系。

🔄 举一反三

1. 若是 6 人循环赛，需要多少天？每天几场？
   查看练习答案与解析

   答案： 5 天；每天 3 场。
   解析： 偶数 (n)：天数 (n-1)，每天 (n/2) 场。

---

四、算法设计题（共 1 小题，18 分）

1. 写出最优二叉搜索树（Optimal BST）问题的动态规划算法（设函数名 binarysearchtree）。（18 分）

查看答案与解析

答案（DP 思想与关键递推）：

• 设关键字为 (k_1,\dots,k_n)，成功查找概率为 (p_1,\dots,p_n)，失败查找概率为 (q_0,\dots,q_n)（落在间隙的概率）。
• 令
  • (e[i][j])：构造包含 (k_i\sim k_j) 的最优 BST 的最小期望代价
  • (w[i][j])：概率权重之和
  • (root[i][j])：最优根

递推（经典形式）： [ w[i][j]=w[i][j-1]+p_j+q_j ] [ e[i][j]=\min_{r\in[i,j]}{e[i][r-1]+e[r+1][j]+w[i][j]} ] 边界：(e[i][i-1]=w[i][i-1]=q_{i-1})。

参考实现（C 风格伪码）：

// p[1..n], q[0..n]
// e, w: 1..n+1 by 0..n
// root: 1..n by 1..n
void binarysearchtree(double p[], double q[], int n,
                      double **e, double **w, int **root)
{
    int i, j, r, l;

    // 初始化空树区间 [i, i-1]
    for (i = 1; i <= n + 1; i++) {
        e[i][i - 1] = q[i - 1];
        w[i][i - 1] = q[i - 1];
    }

    // l 是区间长度
    for (l = 1; l <= n; l++) {
        for (i = 1; i <= n - l + 1; i++) {
            j = i + l - 1;
            e[i][j] = 1e100; // +∞
            w[i][j] = w[i][j - 1] + p[j] + q[j];

            for (r = i; r <= j; r++) {
                double t = e[i][r - 1] + e[r + 1][j] + w[i][j];
                if (t < e[i][j]) {
                    e[i][j] = t;
                    root[i][j] = r;
                }
            }
        }
    }
}

---

难度：⭐⭐⭐
考点：#动态规划 #最优二叉搜索树 #区间DP #期望代价

💡 学习锦囊

📖 相关公式与知识点：

• 这是典型区间 DP：状态由区间 ([i,j]) 决定，枚举根 (r) 做划分
• 时间复杂度：朴素实现 (O(n^3))，空间复杂度 (O(n^2))

易错点

• 忘记初始化空区间 (e[i][i-1]) 与 (w[i][i-1])
• 把 (q)（失败概率）漏掉，导致递推不完整

🔄 举一反三

1. 若只给成功概率 (p_i)，没有失败概率 (q_i)，能否构造标准最优 BST？
   查看练习答案与解析

   答案：严格意义上不完整。
   解析： 标准模型的期望代价需要同时考虑查找失败落在间隙的概率 (q_i)。若题目未给，可要求补充或假设某种 (q) 分布，否则模型不闭合。